Năm 1518 Velázquez ra lệnh ông thực hiện chuyến hành trình khám phá và tìm hiểu bên trong Mexico để thuộc địa hóa vùng đất này. Vào phút chót, do thù hằn cũ giữa Velázquez và Cortés, Velázquez đổi ý và rút lệnh. Cortés phớt lờ sắc lệnh và vẫn triển khai, vào tháng 2 năm 1519. Với khoảng 11 tàu, 500 lính, 13 con ngựa và vài cỗ pháo, ông đổ bộ lên bán đảo Yucata thuộc lãnh thổ Maya.[4] Ở đó, ông gặp một linh mục người Tây Ban Nha Geronimo de Aguilar trước đó bị đắm tàu và bị người Maya bản địa giam cầm một thời gian trước khi đào tẩu được.[4] Aguilar đã học tiếng Chontal Maya trong thời gian bị giam giữ, và vì thế có thể phiên dịch cho Cortés. Vào tháng 3 năm 1519, Cortés chính thức tuyên bố chủ quyền vùng đất thuộc vua Tây Ban Nha. Ông dừng ở Trinidad để lấy thêm lính và ngựa. Sau đó ông đến Tabasco, ở đây ông gặp sự kháng cự của người bản địa nhưng chiến thắng. Ông được ban tặng 20 nữ nô lệ trẻ và họ được cải đạo sang Thiên Chúa giáo.[5] Trong số những người phụ nữ này có La Malinche, sau này là vợ của Cortes. Malinche biết nói hai thứ tiếng Nahuatl và Chontal Maya, do đó bà đã giúp Cortés thương thảo với người Aztec với Aguilar. Thông qua La Malinche, Cortés đã biết được từ người Tabasco về sự thịnh vượng của đế quốc Aztec.

Tháng 7 năm 1519, đội quân của ông chiếm Veracruz: Cortés chiếm quyền của thống đốc Cuba để điều hành dưới sự chỉ đạo trực tiếp của King Charles.[4]